package cn.mengfly.algorithm.search;

import cn.mengfly.algorithm.util.ArrayUtil;

/**
 * Quick Find 算法
 * @author wangp
 */
public class QuickFindUf implements Uf {
    private final int[] is;
    private int count;

    public QuickFindUf(int n) {
        is = ArrayUtil.range(n);
        count = n;
    }

    @Override
    public void union(int p, int q) {
        int pNum = find(p);
        int qNum = find(q);
        // 如果两个分量已经是联通的了，那么就不需要做后续的操作
        if (pNum == qNum) {
            return;
        }

        for (int i = 0; i < is.length; i++) {
            // 将P和Q设置为联通状态，及将他们所在通量下表的值设置为相同的
            if (is[i] == qNum) {
                is[i] = pNum;
            }
        }
        count--;
    }

    @Override
    public int find(int p) {
        return is[(int) p];
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public int count() {
        return count;
    }
}
